#include <cstdio>
#include <algorithm>
#include <queue>
#include <cstring>
#include <vector>
using namespace std;
const int MAXN=10050;
bool prime[MAXN];
void init(){
    memset(prime,true,sizeof(prime));
    prime[0]=false;
    prime[1]=false;
    for(int i=2;i<=10000;i++){
        if(prime[i]){
            if(i*i>MAXN){
                continue;
            }
            for(int j=i*i;j<=10000;j+=i){
                prime[j]=false;
            }
        }
    }
}
struct node{
    int n;
    int c;
    node(int _n,int _c):n(_n),c(_c){}
};
int vis[MAXN];
int bfs(int s,int t){
    queue<node> que;
    que.push(node(s,0));
    memset(vis,0,sizeof(vis));
    while(!que.empty()){
        node tmp=que.front();
        que.pop();
        int tn=tmp.n;
        int num=0;
        if(tn==t){
            return tmp.c;
        }
        for(int j=0;j<10;j++){
            num=(tn/10)*10+j;
            if(prime[num] && !vis[num]){
                que.push(node(num,tmp.c+1));
                vis[num]=1;
            }
            num=(tn%10+tn/100*100)+j*10;
            if(prime[num] && !vis[num]){
                que.push(node(num,tmp.c+1));
                vis[num]=1;
            }
            num=(tn%100+tn/1000*1000)+j*100;
            if(prime[num] && !vis[num]){
                que.push(node(num,tmp.c+1));
                vis[num]=1;
            }
            num=(tn%1000)+j*1000;
            if(j==0){
                continue;
            }
            if(prime[num] && !vis[num]){
                que.push(node(num,tmp.c+1));
                vis[num]=1;
            }
        }
    }
    return -1;
}
int main(void){
    int t,a,b;
    init();
    scanf("%d",&t);
    while(t--){
        scanf("%d%d",&a,&b);
        int ans=bfs(a,b);
        if(ans==-1){
            printf("Impossible\n");
        }
        else{
            printf("%d\n",ans);
        }
    }
    return 0;
}
